package com.leetcode.根据数据结构分类.并查集;

import java.util.*;

/**
 * @author: xiaomi
 * @date: 2021/1/29
 * @description: 1631. 最小体力消耗路径
 * https://leetcode-cn.com/problems/path-with-minimum-effort/
 */
public class B_1631_最小体力消耗路径 {

    public static void main(String[] args) {
        int[][] heights = {{1, 2, 2}, {3, 8, 2}, {5, 3, 5}};
        B_1631_最小体力消耗路径 action = new B_1631_最小体力消耗路径();
        int res = action.minimumEffortPath(heights);
        System.out.println("res = " + res);
    }

    /**
     * 这道题居然是动态规划的，分析如下：
     * 1.无法通过局部解获取全局解，即不能用贪心；
     * 2.如果用回溯，每一条路都需要走到最后，所以不适合；
     * 3.每一步都有状态，以及状态之间的转移，但是 dp(i,j) 不是确定的，会根据前一个坐标的值变化，
     * 所以不适合动态规划;
     * --
     * 使用 Dijkstra 解法：
     * 1.
     * 想了一下目前还是木有思路
     * --
     * 最终还是看了一下题解，使用并查集，这个思路很特别！
     * 由于结果上要求最短的绝对值之差，可以升序排序边，然后一直将边进行连接，直到左上角和右下角能够连接即可。
     *
     * @param heights
     * @return
     */
    public int minimumEffortPath(int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;
        int size = m * n;
        InnerUnionFind unionFind = new InnerUnionFind(size);
        int endIndex = size - 1;

        PriorityQueue<Edge> heap = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.value - o2.value;
            }
        });
        //遍历一遍，将元素添加进去
        //分别遍历行的边和列的边
        //1.将所有的行添加进去
        for (int i = 0; i < m; i++) {
            int index = i * n;
            for (int j = 1; j < n; j++) {
                Edge edge = new Edge(index++, index, Math.abs(heights[i][j - 1] - heights[i][j]));
                heap.offer(edge);
            }
        }

        int nextIndex = 0;
        //2.将所有的列添加进去
        for (int i = 0; i < n; i++) {
            int index = i;
            for (int j = 1; j < m; j++) {
                nextIndex = index + n;
                Edge edge = new Edge(index, nextIndex, Math.abs(heights[j - 1][i] - heights[j][i]));
                index = nextIndex;
                heap.offer(edge);
            }
        }
        int res = 0;
        //此时已经将 边添加入 小顶堆
        while (!unionFind.isSame(0, endIndex)) {
            Edge curEdge = heap.poll();
            res = curEdge.value;
            Iterator<Integer> iterator = curEdge.points.iterator();
            int i1 = iterator.next();
            int i2 = iterator.next();
            unionFind.union(i1, i2);
        }


        return res;

    }

    static class InnerUnionFind {
        int[] parents;
        int[] ranks;

        public InnerUnionFind(int capacity) {
            parents = new int[capacity];
            ranks = new int[capacity];
            for (int i = 0; i < capacity; i++) {
                parents[i] = i;
                ranks[i] = 1;
            }
        }

        int find(int index) {
            if (parents[index] != index) {
                parents[index] = find(parents[index]);
            }
            return parents[index];
        }

        void union(int index1, int index2) {
            int p1 = find(index1);
            int p2 = find(index2);
            if (p1 == p2) {
                return;
            }
            if (ranks[p1] == ranks[p2]) {
                parents[p1] = parents[p2];
                ranks[p2]++;
            } else if (ranks[p1] < ranks[p2]) {
                parents[p1] = parents[p2];
            } else {
                parents[p2] = parents[p1];
            }
        }

        boolean isSame(int index1, int index2) {
            return find(index1) == find(index2);
        }
    }

    class Edge {
        /**
         * 无向边的顶点
         */
        Set<Integer> points = new HashSet<>();

        /**
         * 边的差值
         */
        int value;

        /**
         * 无向边
         *
         * @param p1
         * @param p2
         * @param value
         */
        public Edge(int p1, int p2, int value) {
            this.points.add(p1);
            this.points.add(p2);
            this.value = value;
        }
    }
}
